/*************************************************************************
	> File Name: preorder_thread.cpp
	> Author: 
	> Mail: 
	> Created Time: Sun 28 Jul 2024 08:19:50 PM CST
 ************************************************************************/

#include<iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef struct Node{
	int val;
	int ltag, rtag;
	struct  Node *lchild, *rchild;
} Node;

Node *getNewNode(int val) {
	Node *p = (Node *)malloc(sizeof(Node));
	p->ltag = p->rtag = 0;
	p->lchild = p->rchild = nullptr;
	p->val = val;
	return p;
}
Node *insert(Node *root, int val) {
	if(root == nullptr) return getNewNode(val);
	if(root->val == val) return root;
	if(root->val > val) root->lchild = insert(root->lchild, val);
	else root->rchild = insert(root->rchild, val);
	return root;
}
void preOrder(Node *root) {
	if(root == nullptr) return ;
	printf("%d-> ", root->val);
	if(root->ltag == 0) preOrder(root->lchild);
	if(root->rtag == 0) preOrder(root->rchild);
	return ;
}
void buildThread(Node *root) {
	if(root == nullptr) return ;
	static Node *pre = nullptr;
	// Node *left = root->lchild;
	// Node *right = root->rchild;
	if(root->lchild == nullptr) {
		root->lchild = pre;
		root->ltag = 1;
	}
	if(pre && pre->rchild == nullptr) {
		pre->rchild = root;
		pre->rtag = 1;
	}
	pre = root;
	if(root->ltag == 0) buildThread(root->lchild);
	if(root->rtag == 0) buildThread(root->rchild);
	return ;
}


void outPut(Node *root) {//遍历线索化二叉树
    if (!root) return ;
	Node *p = root;
	while(p) {
		printf("%d ", p->val);
		if(p->rchild && p->rtag == 1 || p->ltag == 1) p = p->rchild;
		else p = p->lchild;
	}
	return ;
}

void clear(Node *root) {
	if(root == nullptr) return ;
	if(root->ltag == 0) clear(root->lchild);
	if(root->rtag == 0) clear(root->rchild);
	free(root);
	return ;
}

#define MAX_N 10
int main() {
	Node *root = nullptr;
	for(int i = 0; i < MAX_N; i++) {
		root = insert(root, rand() % 100);
	}
	preOrder(root);
	printf("\n\n");
	buildThread(root);
	outPut(root);
	printf("\n\n");
	clear(root);
	return 0;
}